Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут прикладної математики та фундаментальних наук Кафедра прикладної математики Курсова робота з курсу «Дискретна математика» на тему «Алгоритми "знизу-вверх" з обмеженими поверненнями. Неканонічний аналіз. Аналізатори з двома магазинами. Відношення передування Колмерауера та їх перевірка»  Зміст Зміст 2 Анотація 3 Annotation 4 Вступ 5 Основна частина 7 Рис. №1 — Таблиця обмеженого контексту для граматики (7) 12 Рис. №2 — (1, 1) обмежено контекстний розпізнавач 12 LL(k) і LR(k) граматики 15 Теорія LL-мов 16 Приклад 17 Основні поняття алгоритму Ерлі 17 Вхід алгоритму: 18 Вихід алгоритму: 18 Алгоритм 18 Висновок 19 Список використаної літератури 20 Анотація Всі ми живемо у столітті інноваційних технологій і жоден з нас не може уявити сьогоднішній день без використання будь-яких програм (пошук інформації в інтернеті, покупка речей у магазині і т.д.), тому постає питання: як вирішити проблему зв’язку людини і програми. На сьогоднішній день техніка навчилася розуміти людей настільки, що програми чи вебсайти знають чого вам потрібно. Але як вказати програмі чого саме я хочу? Тобто недостатньо ввести набір слів, а потрібно вказати якийсь зв’язок між словами, щоб між ними був сенс. Так само комп’ютери розуміють слова, які ми ввели, використовуючи різні граматики. Тому в даній роботі буде показано види граматик, пояснення що вони собою являють та алгоритми і приклади роботи граматик. Annotation We all live in an age of innovative technologies, and nowadays, not any one of us can imagine life without the use of programs (searching information on the internet, purchases things in shops ect.) that is why there is a question about how to solve the problem of connection between people and programs. Today's technologies have learned to understand people as much as possible so that programs or websites know what you want. But how do I let the program know what I really want? In other words it is not enough just to write a list of words, you have to put them in a proper way, making some connection between them, they should make sense. In the same way computers understand words, which we write, using different grammar. That is why in this paper, work would be shown types of grammar, what they mean, and algorithms and examples of working with them. Вступ Існує один клас породжуючих систем, які являються для нас найпершим інтересом — системи, які називаються граматиками. Спершу поняття граматики було формалізовано лінгвістами при вивченні природніх мов. Вони цікавилися не тільки визначенням, що є чи не є правильним представленням мови, але також шукали способи описання структури тверджень. Однією з цілей була розробка формальної граматики, здатної описанти природню мову. Надіючись, що, заклавши в комп’ютер формальну граматику, наприклад, англійської мови, можна зробити її такою, що “розуміє” цю мову, по словесному формулюванні проблем отримають їх вирішення, втілювати за допомогою комп’ютера переклад з одної мови на іншу. Як показує практика використання загальнодоступних програм машинного перекладу, по-справжньому доброго вирішення цієї проблеми в нас поки немає. Але цілком задовільні результати досягнуті в описі і реалізації мов. Зі шкільного досліду відомо, що являє собою граматичний розбір речень. При такому розборі визначається, яке слово є підметом, яке використовується в ролі присудка, які слова відіграють роль означення, додатка, обставини і т.д. При розкладі ми маємо справу з граматичними категоріями: речення, група іменника, група присудка, іменник, дієслово, прислівник і т.д. і користуємося власне кажучи, складовими розкладуваного речення. Накприклад, структура англійського речення: “The little boy ran quickly” можна зобразити у вигляді діаграми: Граматичний розбір речень означає використання правил деякої граматики. Ми їх будемо представляти в наступній формі: 〈 речення 〉 → 〈 група підмета 〉〈 група присудка 〉 〈 група підмета 〉 ...